package 每日一题;

import common.GeneralFunction;

public class No1208尽可能使字符串相等 {

    /**
     * 给你两个长度相同的字符串，s 和 t。
     * 将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销（开销可能为 0），也就是两个字符的 ASCII 码值的差的绝对值。
     * 用于变更字符串的最大预算是 maxCost。在转化字符串时，总开销应当小于等于该预算，这也意味着字符串的转化可能是不完全的。
     * 如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串，则返回可以转化的最大长度。
     * 如果 s 中没有子字符串可以转化成 t 中对应的子字符串，则返回 0。
     *
     * 示例 1：
     * 输入：s = "abcd", t = "bcdf", cost = 3
     * 输出：3
     * 解释：s 中的 "abc" 可以变为 "bcd"。开销为 3，所以最大长度为 3。
     * 示例 2：
     * 输入：s = "abcd", t = "cdef", cost = 3
     * 输出：1
     * 解释：s 中的任一字符要想变成 t 中对应的字符，其开销都是 2。因此，最大长度为 1。
     * 示例 3：
     * 输入：s = "abcd", t = "acde", cost = 0
     * 输出：1
     * 解释：你无法作出任何改动，所以最大长度为 1。
     */

    public int equalSubstring(String s, String t, int maxCost) {

        char[] sArr = s.toCharArray();
        char[] tArr = t.toCharArray();

        int left=0;
        int right=0;
        int maxCount=0;
        int maxInitialCost=maxCost;

        while (right<s.length()){

            if(sArr[right]==tArr[right]){
                //等于,就继续前进
                right++;
            }else{
                //不等于,就计算差值,看是否能补全
                int sub = Math.abs(sArr[right] - tArr[right]);
                if(maxCost>=sub){
                    //可以补全差值,继续前进
                    maxCost-=sub;
                    right++;
                }else{
                    //不可补全差值,left前进right前进,吐出差值
                    //如果一开始本来就没有吃进去呢?吐啥?
                    if(maxCount>0) {//吃了才能吐
                        maxCost += Math.abs(sArr[left] - tArr[left]);
                    }
                    left++;
                    //不可补全,并且当前最大值也吃不进去呢?
                    if(sub>maxInitialCost){
                        right++;//跳过当前
                        left=right;//重置left
                        maxCost=maxInitialCost;//重置maxCost
                    }
                }
            }
            maxCount=Math.max(maxCount,right-left);

        }

        return maxCount;
    }

    //好的解法:滑动窗口应该只会增大或不变不会减小
    public int equalSubstringGood(String s, String t, int maxCost) {
        char[] sArr = s.toCharArray();
        char[] tArr = t.toCharArray();
        int l = 0 ,r = 0;
        int usedCost = 0;
        while(r<s.length()){
            usedCost += Math.abs(tArr[r]-sArr[r]);
            //它是不管如何都会right++;因为结果只与(right-left)差值有关,right++了,left也会++;不会影响最大的结果
            r++;
            if(usedCost>maxCost){
                usedCost -= Math.abs(tArr[l]-sArr[l]);
                l++;
            }
        }
        return s.length()-l;
    }

    //参照写法:滑动窗口只增大不减小,窗口大小就是结果
    public int equalSubstringReference(String s,String t,int maxCost){

        char[] sArr = s.toCharArray();
        char[] tArr = t.toCharArray();
        int left=0;
        int right=0;

        while (right<s.length()){
            int sub=Math.abs(sArr[right]-tArr[right]);
            maxCost-=sub;
            right++;
            if(maxCost<0){
                maxCost+=Math.abs(sArr[left]-tArr[left]);
                left++;
            }
        }
        //窗口只大不小,窗口大小就是结果
        return right-left;
    }

    //参考写法:一开始就计算出两两的差值
    public int equalSubstringReference2(String s,String t,int maxCost){

        int[] subArr=new int[s.length()];
        for (int i = 0; i < subArr.length; i++) {
            subArr[i]=Math.abs(s.charAt(i)-t.charAt(i));
        }
        int left=0;
        int right=0;

        while (right<subArr.length){

            maxCost-=subArr[right];
            if(maxCost<0){
                maxCost+=subArr[left];
                left++;
            }
            right++;
        }

        return right-left;
    }

    public static void main(String[] args) {
        GeneralFunction generalFunction=
                new GeneralFunction(No1208尽可能使字符串相等.class,"abcdca", "bcdfcb",3);
        generalFunction.runAllMethod();
    }

}
